package bTree.LeetCode;

import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class 单词拆分 {
    public boolean wordBreak(String s, List<String> wordDict) {
        int length = s.length();
        boolean []dp=new boolean[length+1];
        dp[0]=true;
        Set<String>set=new HashSet<>(wordDict);
        for (int i = 1; i <= length; i++) {
            for (int j = 0; j < i; j++) {
                String substring = s.substring(j, i);
                if (set.contains(substring)&&dp[j]){
                    dp[i]=true;
                }
            }
        }
        return dp[length];
    }
}